package mo.tags.stack;

import mo.common.TreeNode;

import java.util.Arrays;

public class L654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null) {
            return null;
        }
        int maxIdx = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            }
        }
        TreeNode node = new TreeNode(nums[maxIdx]);
        if (maxIdx > 0) {
            node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxIdx));
        }
        if (maxIdx < nums.length - 1) {
            node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxIdx+1, nums.length));
        }
        return node;
    }

    public static void main(String[] args) {
        L654 test = new L654();
        System.out.println(test.constructMaximumBinaryTree(new int[]{3,2,1,6,0,5}));
    }

}
